package 中等.拓扑排序;

import java.util.*;

/**
 * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中
 *  prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/course-schedule
 */
public class 课程表_207 {

    public static void main(String[] args) {

        int[][] prerequisites = {{1, 0}, {0, 1}};
        System.out.println(canFinish2(2, prerequisites));

    }

    /**
     * 可以看作一个有向图
     * 拓扑排序+广度优先搜索
     * 选择一个入度为0的节点
     * 从图中删除该节点，减去图中由该节点造成的入度
     * 继续选择一个入度为0的节点
     * ...
     * 统计所有节点的入度，将入度为0的节点加入队列，广度搜索
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        // 记录已经学习的课程数量
        int count = 0;
        // 统计入度
        int[] degree = new int[numCourses];
        // 存储当前节点指向下个所有节点
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            List<Integer> curList = map.getOrDefault(prerequisite[1], new ArrayList<>());
            curList.add(prerequisite[0]);
            map.put(prerequisite[1], curList);
            degree[prerequisite[0]]++;
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0) queue.addLast(i);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            count += size;
            while (size-- > 0) {
                Integer curCourse = queue.pollFirst();
                List<Integer> nextList = map.get(curCourse);
                if (nextList == null) continue;
                // 下级节点入度-1
                for (Integer nextCourse : nextList) {
                    degree[nextCourse]--;
                    if (degree[nextCourse] == 0) {  // -1后入度为0加入队列
                        queue.addLast(nextCourse);
                    }
                }
            }
        }
        return count == numCourses;
    }

    /**
     * 用列表存储层级关系
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public static boolean canFinish2(int numCourses, int[][] prerequisites) {
        // 记录已经学习的课程数量
        int count = 0;
        // 统计入度
        int[] degree = new int[numCourses];
        // 存储当前节点指向下个所有节点
        List<List<Integer>> lists = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            lists.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            lists.get(prerequisite[1]).add(prerequisite[0]);
            degree[prerequisite[0]]++;
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0) queue.addLast(i);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            count += size;
            while (size-- > 0) {
                Integer curCourse = queue.pollFirst();
                // 下级节点入度-1
                for (Integer nextCourse : lists.get(curCourse)) {
                    degree[nextCourse]--;
                    if (degree[nextCourse] == 0) {  // -1后入度为0加入队列
                        queue.addLast(nextCourse);
                    }
                }
            }
        }
        return count == numCourses;
    }

    public boolean canFinish3(int numCourses, int[][] prerequisites) {
        // 统计入度
        int[] degree = new int[numCourses];
        // 当前节点指向的所有节点，prerequisites[i] 中的所有课程对 互不相同，不会有重复
        List<Integer>[] lists = new List[numCourses];
        for (int i = 0; i < lists.length; i++) {
            lists[i] = new ArrayList<>();
        }
        // [a,b] b -> a
        for (int[] prerequisite : prerequisites) {
            degree[prerequisite[0]]++;
            lists[prerequisite[1]].add(prerequisite[0]);
        }
        int curFinish = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0) {
                queue.addLast(i);
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            curFinish += size;
            while (size-- > 0) {
                Integer course = queue.pollFirst();
                // 指向的下一个课程入度 -1
                for (Integer nextCourse : lists[course]) {
                    degree[nextCourse]--;
                    // 只有下一个 -1 变化的节点才有可能入度变为 0
                    if (degree[nextCourse] == 0) {
                        queue.addLast(nextCourse);
                    }
                }
            }
        }

        return curFinish == numCourses;
    }

}
